package com.yangli.leecode.mashib.interview;

import java.util.Arrays;

/**
 * @Description
 * @Author liyang
 * @Date 2023/3/29 9:26
 */
public class SixtyTwo {

    //l..r范围上能消除字符串最大长度
    public static int process(int arr[], int l, int r){
        if (l >= r) {
            return 0;
        }
        if (l == r - 1) {
            return ((arr[l] == 0 && arr[r] == 1) || (arr[l] == 2 && arr[l] == 3)) ? 2 : 0;
        }
        int p1 = process(arr, l + 1, r);//不考虑l
        if (arr[l] == 1 || arr[l] == 3) {
            return p1;
        }

        int find = arr[l] == 0 ? 1 : 3;
        int p2 = 0;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] == find) {
                p2 = Math.max(p2, process(arr, l + 1, i - 1) + 2 + process(arr, i + 1, r));
            }
        }
        return Math.max(p1, p2);
    }

    public static int maxSubStr(int arr[]){
        if (arr == null || arr.length == 0) {
            return 0;
        }

        return process(arr, 0, arr.length - 1);
    }

    public static void main(String[] args){
        System.out.println(SixtyTwo.maxSubStr(new int[]{0, 0, 1, 1, 0, 2, 3, 1, 1}));
        System.out.println(SixtyTwo.minSort(new int[]{0, 2, 1, 3, 6, 8, 7, 4, 5}));

        int[] temp = new int[]{0, 2, 1, 3, 6, 8, 7, 5, 4};
        SixtyTwo.nextPermutation(temp);
        System.out.println(Arrays.toString(temp));

        int[][] temp2 = new int[][]{{0, 1, 1, 0, 0, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 1}};
        System.out.println( SixtyTwo.minTotalDistance(temp2));


    }

    //0...n-1数字，无重复快速排序
    public static int minSort(int arr[]){
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            while (arr[i] != i) {
                swap(arr, i, arr[i]);
                ans++;
            }
        }
        return ans;
    }

    public static void swap(int arr[], int i, int j){
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }


    //https://leetcode.cn/problems/next-permutation/
    public static void nextPermutation(int arr[]){
        if (arr == null || arr.length == 0) {
            return;
        }
        int find = -1;
        for (int i = arr.length - 2; i >= 0; i--) {
            if (arr[i] < arr[i + 1]) {
                find = i;
                break;
            }
        }
        if (find == -1) {
            reserve(arr, 0, arr.length - 1);
            return;
        }
        int swap = -1;
        for (int i = arr.length - 1; i > find; i--) {
            if (arr[i] > arr[find]) {
                swap = i;
                break;
            }
        }
        int temp = arr[find];
        arr[find] = arr[swap];
        arr[swap] = temp;
        reserve(arr, find + 1, arr.length - 1);
    }

    public static void reserve(int arr[], int i, int j){
        if (i >= j) {
            return;
        }
        for (int m = i, n = j; m < n; m++, n--) {
            int temp = arr[m];
            arr[m] = arr[n];
            arr[n] = temp;
        }
    }


    public static int minTotalDistance(int arr[][]){
        int[] clo = new int[arr.length];
        int[] row = new int[arr[0].length];

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                if (arr[i][j] == 1) {
                    clo[i] += 1;
                }
            }
        }

        for (int i = 0; i < arr[0].length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (arr[j][i] == 1) {
                    row[i] += 1;
                }
            }
        }
        int pre = clo[0];
        int tail = clo[arr.length - 1];
        int cloP = 0;
        for (int l = 0, r = arr.length - 1; ; ) {

            if (pre > tail) {
                r--;
                tail +=clo[r];
            } else {
                l++;
                pre +=clo[l];

            }
            if (l == r) {
                cloP = pre > tail ? r : l;
                break;
            }
        }
        pre = row[0];
        tail = row[arr[0].length - 1];
        int rowP = 0;
        for (int l = 0, r = arr[0].length - 1; ; ) {
            if (pre > tail) {
                r--;
                tail +=row[r];
            } else {
                l++;
                pre +=row[l];
            }
            if (l == r) {
                rowP = pre > tail ? r : l;
                break;

            }
        }

        int ans = 0;
        for (int i = 0; i < arr.length ; i++) {
            ans += clo[i] * Math.abs(i - cloP);
        }

        for (int i = 0; i < arr[0].length ; i++) {
            ans += row[i] * Math.abs(i - rowP);
        }

        return ans;

    }
}
